import java.util.Arrays;
import java.util.Iterator;

public class Sort {
	public static void main(String[] args) {
		int[] arr = { 1, 6, 3, 8, 34, 6, 2, 8 };
		// buddle(arr);
		// selectSort(arr);
		insertSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 冒泡排序：两两比较，交换位置
	 * 
	 * @param arr
	 */
	static void buddle(int[] arr) {
		// 在最后一轮剩下最后一个元素
		// i < arr.length 最后一个元素自己和自己比较一次
		for (int i = 0; i < arr.length - 1; i++) {
			// 经历一轮比较以后，都会产生一个最大值，
			// 下一轮这个最大值是不参与排序 - i
			// 在循环里面是那当前位置和后一个位置进行比较
			// 所以索引只需要移动到倒数第二个索引位置，需要-1
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 数组元素两两比较，交换位置
				if (arr[j] > arr[j + 1]) {
					int temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 选择排序：从0索引开始，依次和后面的元素比较，经过一轮比较后，最小的元素就出现在最小索引处
	 * 
	 * @param arr
	 */
	static void selectSort(int[] arr) {
		// 定义排序的轮数
		for (int i = 0; i < arr.length - 1; i++) {
			// 获取每一轮的最小索引
			int minIndex = i;
			// 每轮循环从未排序的序列的第一个位置开始排序，j = i
			for (int j = i; j < arr.length; j++) {
				// 假设minIndex位置的元素是最小元素，依次从后面的元素中找到是否
				// 有比minIndex位置的元素还小的元素，如果有把这个元素的索引给minIndex
				if (arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}

			// 找到最小值的索引是minIndex，
			// 这个时候咱们需要和未排序的数列的第一个元素进行交换位置
			// 未排序的序列的开始索引是i
			// 需要索引i位置的元素和minIndex位置的元素进行交换
			int temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
		}
	}

	// 升序
	static void insertSort(int[] arr) {
		// 需要经历多少轮
		for (int i = 1; i < arr.length; i++) {
			// 插入
//			for (int j = i; j > 0; j--) {
//				if (arr[j] < arr[j-1] ) {
//					int temp = arr[j];
//					arr[j] = arr[j-1];
//					arr[j-1] = temp;
//				}
//			}

			int j = i;
			while (j > 1 && arr[j] < arr[j - 1]) {
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
				j--;
			}
		}
	}
}
